class Solution(object):
    # def generateParenthesis(self, n):
    #     """
    #     :type n: int
    #     :rtype: List[str]
    #     """
    #     res = []
    #
    #     def helper(string, left, right):
    #         if left == 0 and right == 0:
    #             res.append(string)
    #             return
    #         if left == right:  # 剩余左右括号数相等，下一个只能用左括号
    #             helper(string+'(', left-1, right)
    #         elif left < right:  # 剩余左括号小于右括号，下一个可以用左括号也可以用右括号
    #             if left > 0:
    #                 helper(string+'(', left-1, right)
    #             helper(string+')', left, right-1)
    #
    #     if n <= 0:
    #         return res
    #     return helper("", n, n)

    # 回溯 + 剪枝
    def generateParenthesis(self, n: int):
        ans = []

        def backtrack(S, left, right):  # DFS
            if len(S) == 2 * n:
                ans.append(''.join(S))
                return
            if left < n:
                backtrack(S+"(", left+1, right)
            if right < left:
                backtrack(S+")", left, right+1)

        backtrack("", 0, 0)
        return ans


if __name__ == "__main__":
    soln = Solution()
    print(soln.generateParenthesis(0))
    print(soln.generateParenthesis(1))
    print(soln.generateParenthesis(2))
    print(soln.generateParenthesis(3))
    print(soln.generateParenthesis(4))
